package com.wang.utils.sort;

import java.util.Arrays;

/**
 * @author 86173
 * @date 2021/7/30 18:40
 * 第一种思路，插入时是交换比较的值  耗时较长
 * 第二种思路，插入时移动位置		速度很快
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] arr = {1,2,5,3,6,7,0,8,4,9};
		shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public static void shellSort(int[] arr) {
		int length = arr.length;
		int temp;
		int count = 0;
		//按照一定规则先将数组拆分分组，不断的分组
		//step 为步长
		for (int step = length / 2; step >= 1; step /= 2) {
			//遍历各组，进行排序
			//按照插入排序进行拆分的数组进行排序
			for (int i = step; i < length; i++) {
				temp = arr[i];
				int j = i - step;
				while (j >= 0 && arr[j] > temp) {
					//条件成立后，是将arr[step] 与arr[step+5] 进行交换
					arr[j + step] = arr[j];
					j -= step;
				}
				//退出虚幻找到了temp的位置
				arr[j + step] = temp;
			}
			++count;
			System.out.println("第"+count+"次:"+Arrays.toString(arr));
		}
	}

}
